package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import ru.amse.stroganova.graph.AbstractGraph;
import ru.amse.stroganova.graph.DirectedGraph;
import ru.amse.stroganova.graph.Edge;
import ru.amse.stroganova.graph.Vertex;

/**
 * Presents maximum flow search with Ford-Falkerson algorythm.
 * 
 * @author Dasha Stroganova
 *
 */
public class FordFalkersonAlgorythm {

	private static final String ERROR_MESSAGE = "The graph is not a flow network - there are edges with negative capacities.";

	private boolean hasNegativeCapacities;
	
	private final AbstractGraph graph;
	
	private AbstractGraph residualNetwork;
	
	private final Map<Edge, Integer> maximumFlow;
	
	private Map<Edge, Edge> residualInitEdgesMap;
	
	private Vertex residualSource;
	
	private Vertex residualSink;
	
	private final Map<Vertex, Map<Vertex, Integer>> flow;
	
	private int maxFlowSize = 0;
	
	/**
	 * Creates new Ford-Falkerson algorythm for the given graph and source and sink.
	 * 
	 * @param graph
	 * @param source
	 * @param sink
	 */
	public FordFalkersonAlgorythm(AbstractGraph graph, Vertex source, Vertex sink) {
		maximumFlow = new HashMap<Edge, Integer>();
		this.graph = graph;
		flow = new HashMap<Vertex, Map<Vertex,Integer>>();
		
		initFlow();
		
		if (!hasNegativeCapacities()) {
			createResidualNetwork(source, sink);
			findMaxFlow(source, sink);
			for (Edge edge : maximumFlow.keySet()) {
				if (edge.getSource().equals(source)) {
					maxFlowSize += maximumFlow.get(edge);
				}
			}
		}
	}
	
	private void initFlow() {
		for (Vertex vertex : graph.getVertices()) {
			flow.put(vertex, new HashMap<Vertex, Integer>());
		}
		for (Vertex vertex : graph.getVertices()) {
			for (Edge edge : vertex.getOutgoingEdges()) {
				if (edge.getWeight() < 0) {
					hasNegativeCapacities = true;
					return;
				}
				flow.get(edge.getSource()).put(edge.getDestination(), 0);
				flow.get(edge.getDestination()).put(edge.getSource(), 0);
			}
		}
	}
	
	private void createResidualNetwork(Vertex source, Vertex sink) {
		Map<Vertex, Vertex> initResidualVerticesMap = new HashMap<Vertex, Vertex>();
		residualInitEdgesMap = new HashMap<Edge, Edge>();
		residualNetwork = new DirectedGraph();
		
		for (Vertex vertex : graph.getVertices()) {
			Vertex residualVertex = new Vertex();
			initResidualVerticesMap.put(vertex, residualVertex);
			residualNetwork.addVertex(residualVertex);
		}
		residualSink = initResidualVerticesMap.get(sink);
		residualSource = initResidualVerticesMap.get(source);
		for (Vertex vertex : graph.getVertices()) {
			for (Edge edge : vertex.getOutgoingEdges()) {
				Edge residualEdge = new Edge(initResidualVerticesMap.get(edge.getSource()), initResidualVerticesMap.get(edge.getDestination()), edge.getWeight());
				residualInitEdgesMap.put(residualEdge, edge);
				residualNetwork.addEdge(residualEdge);
			}
		}
	}
	
	private void findMaxFlow(Vertex source, Vertex sink) {
		for (List<Edge> path = findPath(residualNetwork, residualSource, residualSink); path.size() != 0; path = findPath(residualNetwork, residualSource, residualSink)) {
			int flowAddition = minPathCapacity(path);
			for (Edge residualEdge : path) {
				Edge graphEdge = residualInitEdgesMap.get(residualEdge);
				int newFlow = flow.get(graphEdge.getSource()).get(graphEdge.getDestination()) + flowAddition;
				flow.get(graphEdge.getSource()).put(graphEdge.getDestination(), newFlow);
				flow.get(graphEdge.getDestination()).put(graphEdge.getSource(), -newFlow);
				if (newFlow == graphEdge.getWeight()) {
					residualNetwork.disconnect(residualEdge.getSource(), residualEdge.getDestination());
				} else {
					residualEdge.setWeight(graphEdge.getWeight() - newFlow);
				}
				if (!residualNetwork.areConnected(residualEdge.getDestination(), residualEdge.getSource())) {
					residualNetwork.addEdge(new Edge(residualEdge.getDestination(), residualEdge.getSource(), flowAddition));
				} else {
					Edge oppositeEdge = residualNetwork.getConnectingEdge(residualEdge.getDestination(), residualEdge.getSource());
					oppositeEdge.setWeight(oppositeEdge.getWeight() + newFlow);
				}
			}
		}
		
		for (Vertex vertex : graph.getVertices()) {
			for (Edge edge : vertex.getOutgoingEdges()) {
				if (flow.get(edge.getSource()).get(edge.getDestination()) > 0) {
					maximumFlow.put(edge, flow.get(edge.getSource()).get(edge.getDestination()));
				}
			}
		}
	}
	
	private List<Edge> findPath(AbstractGraph graphToSearch, Vertex source, Vertex sink) {
		List<Edge> path = new ArrayList<Edge>();
		Queue<Vertex> queue = new LinkedList<Vertex>();
		Map<Vertex, Vertex> predesessors = new HashMap<Vertex, Vertex>();
		Map<Vertex, Boolean> wasVisited = new HashMap<Vertex, Boolean>();
		
		if (graphToSearch.getVertices().size() > 0) {
			wasVisited.put(source, true);
			queue.offer(source);
		}
		
		while (!queue.isEmpty()) {
			Vertex currentVertex = queue.poll();
			for (Edge edge : currentVertex.getOutgoingEdges()) {
				Vertex opposite = edge.getOppositeVertex(currentVertex);
				if (wasVisited.get(opposite) == null) {
					wasVisited.put(opposite, true);
					predesessors.put(opposite, currentVertex);
					queue.offer(opposite);
				}
				if (opposite.equals(sink)) {
					for (Vertex vertex = opposite; predesessors.get(vertex) != null; vertex = predesessors.get(vertex)) {
						path.add(graphToSearch.getConnectingEdge(predesessors.get(vertex), vertex));
					}
					return path;
				}
			}
		}
		
		return path;
	}
	
	private int minPathCapacity(List<Edge> path) {
		int min = Integer.MAX_VALUE;
		for (Edge edge : path) {
			if (min > edge.getWeight()) {
				min = edge.getWeight();
			}
		}
		return min;
	}
	
	/**
	 * If any errors exist return error message.
	 * 
	 * @return error message if error exists; empty string otherwise
	 */
	public String getErrorMessage() {
		return hasNegativeCapacities ? ERROR_MESSAGE : "";
	}
	
	/**
	 * Checks whether given graph had edges with negative capacities.
	 * 
	 * @return the hasNegativeCapacities
	 */
	public boolean hasNegativeCapacities() {
		return hasNegativeCapacities;
	}
	
	/**
	 * Return map with edges and flows on them. Throws new {@link IllegalStateException} if there are edges with negative capacities.
	 * 
	 * @return the max flow
	 */
	public Map<Edge, Integer> getMaximumFlow() {
		if (hasNegativeCapacities()) {
			throw new IllegalStateException("This graph has negative capacities. Ford-Falkerson doesn't work correctly.");
		}
		return maximumFlow;
	}
	
	/**
	 * Return maximum flow size. Throws new {@link IllegalStateException} if there are edges with negative capacities.
	 * 
	 * @return max flow size
	 */
	public int getMaximumFlowSize() {
		if (hasNegativeCapacities()) {
			throw new IllegalStateException("This graph has negative capacities. Ford-Falkerson doesn't work correctly.");
		}
		return maxFlowSize;
	}
}
